package zhanyuduilie

import "math"

func MaxSlidingWindow(nums []int, k int) []int {
	cur := durMax(nums[:k])
	n := len(nums)
	ans := make([]int, 0)
	ans = append(ans, cur)
	for i := k; i < n; i++ {
		if cur == nums[i-k] {
			cur = durMax(nums[i-k+1 : i])
		}
		cur = max(cur, nums[i])
		ans = append(ans, cur)
	}
	return ans
}

func durMax(nums []int) int {
	ans := math.MinInt32
	for i := 0; i < len(nums); i++ {
		ans = max(ans, nums[i])
	}
	return ans
}

// 维护一个单调队列

type MyQueue1 struct {
	queue []int
}

func (q *MyQueue1) Push(x int) {
	// 单调队列重点在于添加：每次添加的小于尾部元素直接添加，若大于，去除尾部元素然后添加，基于上述内容可知：必须是全面比较，使用for而不是if
	for !q.IsEmpty() && q.Back() < x {
		q.queue = q.queue[:len(q.queue)-1]
	}
	q.queue = append(q.queue, x)
}
func (q *MyQueue1) Pop(val int) {
	if !q.IsEmpty() && val == q.Front() {
		q.queue = q.queue[1:]
	}
}
func (q *MyQueue1) IsEmpty() bool {
	return len(q.queue) == 0
}
func (q *MyQueue1) Front() int {
	return q.queue[0]
}
func (q *MyQueue1) Back() int {
	return q.queue[len(q.queue)-1]
}
func Dandiaoduilie(nums []int, k int) []int {
	ans := make([]int, 0)
	q := MyQueue1{}
	for i := 0; i < k; i++ {
		q.Push(nums[i])
	}
	ans = append(ans, q.Front())
	for i := k; i < len(nums); i++ {
		// 从这里实现的比较、删除和添加
		q.Pop(nums[i-k])
		q.Push(nums[i])
		ans = append(ans, q.Front())
	}
	return ans
}
